package com.yangzhe.algorithm.c042;

// 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
// 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
// 如果不存在每个袋子都装满的方案返回-1
public class Code01_AppleMinBags {

    /**
     * 暴力递归思路
     * <p>
     * 至少袋子 n = f(restApple)
     *
     * @param apple
     * @return
     */
    public static int bags1(int apple) {
        int n = f(apple);
        if (n == 0 || n == Integer.MAX_VALUE) {
            return -1;
        } else {
            return n;
        }
    }

    public static int f(int restApple) {
        if (restApple == 0) {
            return 0;
        }

        // 如果剩余袋子小于0，则不够 6个或8个 返回一个无效值
        if (restApple <= 0) {
            return Integer.MAX_VALUE;
        }

        // 分别递归尝试装8个、6个
        int n1 = f(restApple - 8);
        int n2 = f(restApple - 6);

        int n = Math.min(n1, n2);
        // 如果装 8个或6个 都不行，则这种方式不行
        if (n == Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else {
            // + 1是因为本次装了 8个或6个
            return n + 1;
        }
    }


    /**
     * 打表找到规律
     * 大于18，每8个一组，偶数递增
     *
     * @param apple
     * @return
     */
    public static int bags2(int apple) {
        // 奇数肯定不满足
        if ((apple & 1) != 0) {
            return -1;
        }

        if (apple == 6 || apple == 8) {
            return 1;
        } else if (apple == 12 || apple == 14 || apple == 16) {
            return 2;
        }

        if (apple < 18) {
            return -1;
        }

        return ((apple - 18) / 8) + 3;
    }

    public static void main(String[] args) {
        for (int apple = 0; apple < 100; apple++) {
            System.out.println(apple + " : " + bags1(apple));
            System.out.println(apple + " : " + bags2(apple));
        }
    }

}
